package PersonStu.sanqi;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Author by KoVaVo
 * @Date 2023-01-02 15:21
 * @Desc: 滑动窗口求最大值
 * 给定一个数组和滑动窗口的大小，
 * 求每一次滑动窗口后的最大的那个数字，
 * 然后放到数组中。返回最后的数组
 *
 * arr = [4,3,5,4,3,3,6,7] => [5,5,5,4,6,7]
 */
public class code_24_SlidingWindowMaxArray {

    public static int [] getMax(int [] nums,int W){
        if(nums == null || nums.length == 0){
            return nums;
        }
        int N = nums.length;
        int [] res = new int[N - W + 1];
        //qMax放的是下标索引
        LinkedList<Integer> qMax = new LinkedList<>();
        int index = 0;
        //定义R为右边界
        for (int R = 0; R < nums.length; R++) {
            //将滑动窗口中的值，放到LinkedList中（定义的双端队列）
            //将当前的值，和我队列中的值做比较。如果没有我当前的值大那么弹出去，这样就保证了在队列的头部的值是最大的。
            while (!qMax.isEmpty() && nums[qMax.peekLast()] <= nums[R]){
                qMax.pollLast();//直接弹出后从队列中删除
            }
            qMax.addLast(R);
            if(qMax.peekFirst() == R - W){
                qMax.pollFirst();
            }
            //开始放到res中
            if(R >= W - 1){
                res[index++] = nums[qMax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int [] nums = {4,3,5,4,3,3,6,7};
        int[] max = getMax(nums, 3);
        System.out.println(Arrays.toString(max));
    }
}
